
/*
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 * SPDX-License-Identifier: GPL-3.0+
 * License-Filename: LICENSE
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#include "splay-tree.h"
#include "main.h"
#include "mem.h"
#include "options.h"
#include "color.h"
#include "nes.h"
#include "folding.h"
#include "lmain.h"
#include "parse.h"
#include "uniqnode.h"
#include "uniqnodeid.h"
#include "uniqstring.h"

/* drawing scaled 1:1 (x,y) size */
int maxx = 0;
int maxy = 0;

/* number of nodes+edges in drawing after folding etc. including invisible edges */
int n_drawing_nodes = 0;
int n_drawing_edges = 0;

/* input number of nodes */
int n_input_nodes = 0;

/* input number of singlenodes */
int n_input_singlenodes = 0;

/* input number of edges */
int n_input_edges = 0;

/* input number of edges */
int n_input_revedges = 0;

/* input number of selfedges */
int n_input_selfedges = 0;

/* input number of edge labels */
int n_input_edgelabels = 0;

/* input number of subgraphs */
int n_input_subgraphs = 0;

/* cycles in folded graph determined in folding() */
int n_folded_cycles = 0;

/* cycles in folded graph after reverse edges determined in folding() (should be 0) */
int n_folded_cycles_revedges = 0;

/* node data */
struct rg_node_struct {
	char *name;		/* uniq name */
	int id;			/* unique identifier */
	int layer;		/* layer level or -1 if undefiled */
	int position;		/* pos within layer or -1 if undefined */
};

/* edge data */
struct rg_edge_struct {
	struct rg_node_struct *up_node;
	struct rg_node_struct *down_node;
};

/* table for layers */
struct rg_layer_struct {
	int number_of_nodes;
	struct rg_node_struct **nodes;
};

/* number of layers */
static int rg_number_of_layers = 0;

/* layers table */
static struct rg_layer_struct **rg_layers = NULL;

/* nodes */
static struct rg_node_struct **rg_master_node_list = NULL;

/* edges */
static struct rg_edge_struct **rg_master_edge_list = NULL;

/**
 * New nodes randomly selected to be adjacent to the current node are put at
 * the rear of the master node list; this global variable keeps track of that
 * rear position; this rear position also determines the number of nodes that
 * have been added to the tree, hence the name
 */
static int rg_number_of_tree_nodes = 0;

/* number of nodes */
static int rg_number_of_nodes = 0;

/* number of edges */
static int rg_number_of_edges = 0;

/* random node direction table */
static int *rg_going_up = NULL;

/**
 * The number of layers that have no nodes on them. Used to ensure that
 * branching does not cause the number of layers to be less than what was
 * requested.
 */
static int rg_layers_remaining = 0;

/*
 *
 */

/* nodes as parsed indexed on (int) uniq_node_number */
splay_tree sp_parsednl = (splay_tree) 0;

/* uniq node number for regular, dummy, edgelabel and subgraph summary nodes */
int uniq_node_number = 0;

/* edges as parsed indexed on unique edge number */
splay_tree sp_parsedel = (splay_tree) 0;

/* work edges as parsed indexed on unique edge number */
splay_tree sp_parsedwel = (splay_tree) 0;

/* uniq edge number for regular and dummy edges */
static int uniq_edge_number = 0;

/* subgraphs as parsed indexed on unique subgraph number */
splay_tree sp_parsedsgl = (splay_tree) 0;

/* subgraphs as parsed indexed on unique subgraph number */
splay_tree sp_parsedwsgl = (splay_tree) 0;

/* uniq subgraph number */
static int uniq_subgraph_number = 0;

/* summary nodes in subgraphs */
splay_tree sp_summarynl = (splay_tree) 0;

/* summary nodes in subgraphs working list */
splay_tree sp_wsummarynl = (splay_tree) 0;

/* nodes in root graph */
splay_tree sp_rootnl = (splay_tree) 0;

/* edges connected to nodes in root graph */
splay_tree sp_rootel = (splay_tree) 0;

/* artificial nodes as dummy and edge-label nodes */
splay_tree sp_virtualnl = (splay_tree) 0;

/* artificial edges connecting to dummy and edge-label nodes */
splay_tree sp_virtualel = (splay_tree) 0;

/* parsed work node list */
splay_tree sp_parsedwnl = (splay_tree) 0;

/* draw nodes list */
struct drawn *drawnl = NULL;

/* draw nodes list end */
struct drawn *drawnl_end = NULL;

/* draw edges list */
struct drawe *drawel = NULL;

/* draw edges list end */
struct drawe *drawel_end = NULL;

/* draw layer information */
struct dli **dlip = NULL;

/* draw layer information number of levels */
int dli_nlevels = 0;

/* forward decl. */
static void parsednodes_clear(void);
static void parsededges_clear(void);
static void parsedsubgraph_clear(void);
static void parsednl_clear(void);
static void parsedel_clear(void);
static void parsedsgl_clear(void);
static void parsedsgl_add_node(struct unode *un);
static void parsedsgl_add_edge(struct uedge *ue);
static int rg_rand(int maxval);
static void rg_backgroundcolor(void);
static unsigned char rg_nodeshape(void);
static unsigned int rg_nodecolor(void);
static unsigned int rg_nodetextcolor(void);
static unsigned int rg_edgecolor(void);
static int rg_edgestyle(void);
static void rg_dag(int num_nodes, int desired_num_edges, int num_layers, int branching_factor);
static void rg_tree(int num_nodes, int num_layers, int branching_factor);
static void rg_create_master_node_list(int num_nodes);
static void rg_init_layers(int num_layers);
static void rg_init_node_directions(int num_nodes);
static void rg_add_node_to_layer(struct rg_node_struct *node, int layer);
static void rg_add_node_to_list(struct rg_node_struct *node);
static void rg_assign_child_layer_and_direction(int parent, int child);
static void rg_add_edge(struct rg_node_struct *upper_node, struct rg_node_struct *lower_node);
static int rg_pair_already_exists(int first_node_index, int second_node_index);
static char *rg_numberstring(void);
static char *rg_labelstring(void);
static char *rg_fontsize_numberstring(void);

/* init at start */
void once_init(void)
{

	/* optional html page with color names */
	if (option_colorpage) {
		colorcode_html("./tuxsee-colors.html");
	}

	/* default drawing background color is white */
	bgcr = 0xff;
	bgcg = 0xff;
	bgcb = 0xff;

	return;
}

/* clear */
void nes_clear(void)
{

	/* clear nodes in root graph */
	rootnl_clear();

	/* clear edges connected to nodes in root graph */
	rootel_clear();

	/* clear artificial nodes */
	virtualnl_clear();

	/* clear artificial edges */
	virtualel_clear();

	/* clear data inside subgraph data */
	parsedsubgraph_clear();

	/* clear subgraph list itself */
	parsedsgl_clear();

	/* clear data inside edges */
	parsededges_clear();

	/* clear edgelist itself */
	parsedel_clear();

	/* clear data inside nodes */
	parsednodes_clear();

	/* clear parsed nodes itself */
	parsednl_clear();

	/* clear node/edge/subgraph/drawnode/drawedge lists */
	summarynl_clear();

	/* parsed working node lists */
	parsedwnl_clear();
	parsedwel_clear();
	dli_clear();
	drawnl_clear();
	drawel_clear();

	/* nodes as parsed indexed on (int) uniq_node_number */
	sp_parsednl = (splay_tree) 0;

	/* uniq node number for regular, dummy, edgelabel and subgraph summary nodes */
	uniq_node_number = 0;

	/* edges as parsed indexed on unique edge number */
	sp_parsedel = (splay_tree) 0;

	/* work edges as parsed indexed on unique edge number */
	sp_parsedwel = (splay_tree) 0;

	/* uniq edge number for regular and dummy edges */
	uniq_edge_number = 0;

	/* subgraphs as parsed indexed on unique subgraph number */
	sp_parsedsgl = (splay_tree) 0;

	/* uniq subgraph number */
	uniq_subgraph_number = 0;

	/* summary nodes in subgraphs */
	sp_summarynl = (splay_tree) 0;

	/* summary nodes in subgraphs */
	sp_wsummarynl = (splay_tree) 0;

	/* nodes in root graph */
	sp_rootnl = (splay_tree) 0;

	/* edges connected to nodes in root graph */
	sp_rootel = (splay_tree) 0;

	/* artificial nodes as dummy and edge-label nodes */
	sp_virtualnl = (splay_tree) 0;

	/* artificial edges connecting to dummy and edge-label nodes */
	sp_virtualel = (splay_tree) 0;

	/* parsed work node list */
	sp_parsedwnl = (splay_tree) 0;

	/* draw nodes list */
	drawnl = NULL;

	/* draw nodes list end */
	drawnl_end = NULL;

	/* draw edges list */
	drawel = NULL;

	/* draw edges list end */
	drawel_end = NULL;

	/* no drawing layer info */
	dli_nlevels = 0;
	dlip = NULL;

	return;
}

/* only once calculate the graph in initial state */
void calculate_init(void)
{
	/* set (x,y) size of node/edge/subgraph labels, depends on a gtk+ cr */
	textsizes();

	/* count selfedges at nodes */
	markselfedges();

	/* indicate single nodes */
	marksinglenodes();

	/* input statistics */
	input_stats();

	return;
}

/* calculate the graph */
void calculate(void)
{

	/* clear folding data */
	folding_clear();

	/* clear layouter data */
	mainl_clear();

	/* drawing size is 0 */
	maxx = 0;
	maxy = 0;

	/* number of nodes+edges in drawing after folding etc. including invisible edges */
	n_drawing_nodes = 0;
	n_drawing_edges = 0;

	/* handle graph folding */
	folding();

	/* check if there are working nodes */
	if (splay_tree_has_data(sp_parsedwnl) == 0) {
		printf("%s(): fixme no working nodes\n", __FUNCTION__);
		fflush(stdout);

		maxx = 1;
		maxy = 1;

		/* update status text in gui */
		update_statusline(NULL);

		return;
	}

	/* put nodes in levels */
	if (nodesinlevels()) {
		/* horizontal edges */
	}

	/* split long edges with dummy nodes */
	longedges();

	/* copy parsed data into layouter */
	parsed2layouter();

	/* run the layouter edge crossing reduction */
	layout_graph();

	/* copy layouter data into draw data */
	layouter2draw();

	/* update status text in gui */
	update_statusline(NULL);

	return;
}

/* clear all data just before parsing new data or random data */
void prepare4newdata(void)
{

	/* clear all parser data */
	parse_clear();

	/* clear folding data */
	folding_clear();

	/* clear layouter data */
	mainl_clear();

	/* clear node/edge/subgraph parsed structures */
	nes_clear();

	/* clear node database */
	uniqnode_clear();

	/* clear node database */
	uniqnodeid_clear();

	/* clear strings */
	uniqstring_clear();

	/* color database */
	colorcode_clear();

	/* memory statistics */
	mymemstats();

	/* default drawing background color is white */
	bgcr = 0xff;
	bgcg = 0xff;
	bgcb = 0xff;

	/* drawing size is 0 */
	maxx = 0;
	maxy = 0;

	/* set default layout algo from default or commandline option */
	set_default_algo();

	return;
}

/* clear node list of nodes in root graph */
void rootnl_clear(void)
{
	sp_rootnl = splay_tree_delete(sp_rootnl);
	return;
}

/* clear edge list of edges connecting to nodes in root graph */
void rootel_clear(void)
{
	sp_rootel = splay_tree_delete(sp_rootel);
	return;
}

/* clear virtual nodes list and nodes itself */
void virtualnl_clear(void)
{
	struct unode *un = (struct unode *)0;
	splay_tree_node spn = (splay_tree_node) 0;

	if (splay_tree_has_data(sp_virtualnl)) {

		spn = splay_tree_min(sp_virtualnl);

		while (spn) {
			un = (struct unode *)spn->value;

			/* clear part of edge list in unode */
			un->sp_poe = splay_tree_delete(un->sp_poe);

			spn = splay_tree_successor(sp_virtualnl, spn->key);
		}
	}

	sp_virtualnl = splay_tree_delete(sp_virtualnl);

	return;
}

/* clear virtual edges list and edges itself */
void virtualel_clear(void)
{
	sp_virtualel = splay_tree_delete(sp_virtualel);
	return;
}

/* free parsed data in the struct */
static void parsednodes_clear_freer(struct fld *root)
{
	int ix = 0;
	struct fld *tmpf = NULL;
	ix = 0;
	tmpf = NULL;

	/* should not happen */
	if (root == NULL) {
		printf("%s(): shouldnothappen\n", __FUNCTION__);
		fflush(stdout);
		return;
	}

	if (option_memlog || 0) {
		printf("%s(): root=%p root->f=%p\n", __FUNCTION__, (void *)root, (void *)root->f);
		if (root->f) {
			printf("%s(): %d elements: ", __FUNCTION__, root->nf);
			ix = 0;
			for (;;) {
				if (root->f[ix] == NULL) {
					break;
				}
				printf("%p (%d) ", (void *)root->f[ix], ix);
				ix++;
			}
			printf("\n");
		}
	}

	ix = 0;

	/* scan all ix */
	for (;;) {

		if (root->f == NULL) {
			break;
		}

		tmpf = root->f[ix];

		if (tmpf == NULL) {
			/* last element in list */
			break;
		}
		parsednodes_clear_freer(tmpf);
		myfree(tmpf, __FUNCTION__, __LINE__);
		root->f[ix] = NULL;
		ix++;
	}

	if (root->f) {
		myfree(root->f, __FUNCTION__, __LINE__);
	}

	root->f = NULL;

	return;
}

/* clear node data inside the nodes. verified this is oke. */
static void parsednodes_clear(void)
{
	splay_tree_node spn = (splay_tree_node) 0;
	struct unode *un = (struct unode *)0;

	if (option_memlog || 0) {
		if (splay_tree_has_data(sp_parsednl)) {
			spn = splay_tree_min(sp_parsednl);

			while (spn) {
				un = (struct unode *)spn->value;
				printf("%s(): clear node number=%d\n", __FUNCTION__, un->number);
				spn = splay_tree_successor(sp_parsednl, spn->key);
			}
		}
	}

	if (splay_tree_has_data(sp_parsednl)) {

		spn = splay_tree_min(sp_parsednl);

		while (spn) {
			un = (struct unode *)spn->value;

			if (option_memlog) {
				printf("%s(): %p for un->f node-number=%d\n", __FUNCTION__, (void *)un->f, un->number);
			}

			/* clear optional fields in label */
			if (un->f) {
				parsednodes_clear_freer(un->f);
				myfree(un->f, __FUNCTION__, __LINE__);
				un->f = NULL;
			}

			/* clear part of edge list */
			un->sp_poe = splay_tree_delete(un->sp_poe);

			spn = splay_tree_successor(sp_parsednl, spn->key);
		}
	}

	/* parsed node list is cleared later */

	return;
}

/* clear data inside edges */
static void parsededges_clear(void)
{

	if (splay_tree_has_data(sp_parsedel)) {
		/* clear data inside the edge struct */
	}

	return;
}

/* clear subgraph data */
static void parsedsubgraph_clear_subg(struct usubg *subg)
{
	struct usubg *sg = (struct usubg *)0;
	splay_tree_node spn = (splay_tree_node) 0;

	/* nodes rooted in this subgraph */
	subg->sp_nl = splay_tree_delete(subg->sp_nl);

	/* edges connecting to this subgraph */
	subg->sp_el = splay_tree_delete(subg->sp_el);

	/* summary node part of edge list */
	if (subg->summaryn) {

		/* edges connecting to this summary node */
		subg->summaryn->sp_poe = splay_tree_delete(subg->summaryn->sp_poe);

		/* free summary node itself */
		myfree(subg->summaryn, __FUNCTION__, __LINE__);

		subg->summaryn = NULL;
	}

	/* subgraphs rooted in this subgraph */
	if (splay_tree_has_data(subg->sp_sg)) {

		spn = splay_tree_min(subg->sp_sg);

		while (spn) {
			sg = (struct usubg *)spn->value;
			parsedsubgraph_clear_subg(sg);
			spn = splay_tree_successor(subg->sp_sg, spn->key);
		}

		subg->sp_sg = splay_tree_delete(subg->sp_sg);
	}

	return;
}

/* clear data inside subgraph data */
static void parsedsubgraph_clear(void)
{
	splay_tree_node spn = (splay_tree_node) 0;
	struct usubg *sg = (struct usubg *)0;

	if (splay_tree_has_data(sp_parsedsgl)) {

		spn = splay_tree_min(sp_parsedsgl);

		while (spn) {
			sg = (struct usubg *)spn->value;
			parsedsubgraph_clear_subg(sg);
			spn = splay_tree_successor(sp_parsedsgl, spn->key);
		}

	}

	return;
}

/* clear node list */
static void parsednl_clear(void)
{
	sp_parsednl = splay_tree_delete(sp_parsednl);
	/* uniq node number for regular, dummy, edgelabel and subgraph summary nodes */
	uniq_node_number = 0;
	return;
}

/* clear summary nodes list in subgraphs */
void summarynl_clear(void)
{
	/* summary nodes in subgraphs */
	sp_summarynl = splay_tree_delete(sp_summarynl);

	/* summary nodes in subgraphs */
	sp_wsummarynl = splay_tree_delete(sp_wsummarynl);

	return;
}

/* clear working node list */
void parsedwnl_clear(void)
{

	/* */
	sp_parsedwnl = splay_tree_delete(sp_parsedwnl);

	return;
}

/* clear edge list */
static void parsedel_clear(void)
{

	sp_parsedel = splay_tree_delete(sp_parsedel);

	/* uniq edge number for regular and dummy edges */
	uniq_edge_number = 0;

	return;
}

/* clear working edge list */
void parsedwel_clear(void)
{

	/* */
	sp_parsedwel = splay_tree_delete(sp_parsedwel);

	return;
}

/* clear subgraph list */
static void parsedsgl_clear(void)
{
	/* subgraphs as parsed indexed on unique subgraph number */
	sp_parsedsgl = splay_tree_delete(sp_parsedsgl);

	/* subgraph working data */
	sp_parsedwsgl = splay_tree_delete(sp_parsedwsgl);

	/* uniq subgraph number */
	uniq_subgraph_number = 0;

	return;
}

/* draw node list clear */
void drawnl_clear(void)
{
	struct drawn *ptr = NULL;
	struct drawn *tmpptr = NULL;

	if (drawnl == NULL) {
		return;
	}

	ptr = drawnl;

	while (ptr) {
		tmpptr = ptr->next;
		memset(ptr, 0, sizeof(struct drawn));
		myfree(ptr, __FUNCTION__, __LINE__);
		ptr = tmpptr;
	}

	/* draw nodes list */
	drawnl = NULL;

	/* draw nodes list end */
	drawnl_end = NULL;

	return;
}

/* draw edge list clear */
void drawel_clear(void)
{
	struct drawe *ptr = NULL;
	struct drawe *tmpptr = NULL;

	if (drawel == NULL) {
		return;
	}

	ptr = drawel;

	while (ptr) {
		tmpptr = ptr->next;
		memset(ptr, 0, sizeof(struct drawe));
		myfree(ptr, __FUNCTION__, __LINE__);
		ptr = tmpptr;
	}

	/* draw edges list */
	drawel = NULL;

	/* draw edges list end */
	drawel_end = NULL;

	return;
}

/* draw layer info clear */
void dli_clear(void)
{
	int i = 0;
	struct dli *lp = NULL;
	struct ddn *nptr = NULL;
	struct ddn *nptrtmp = NULL;
	struct dde *eptr = NULL;
	struct dde *eptrtmp = NULL;

	/* check if data */
	if (dli_nlevels == 0) {
		/* no layers data */
		dli_nlevels = 0;
		dlip = NULL;
		return;
	}

	/* clear all layers */
	for (i = 0; i < dli_nlevels; i++) {
		lp = dlip[i];
		nptr = lp->nl;
		while (nptr) {
			nptrtmp = nptr->next;
			memset(nptr, 0, sizeof(struct ddn));
			myfree(nptr, __FUNCTION__, __LINE__);
			nptr = nptrtmp;
		}
		eptr = lp->el;
		while (eptr) {
			eptrtmp = eptr->next;
			memset(eptr, 0, sizeof(struct dde));
			myfree(eptr, __FUNCTION__, __LINE__);
			eptr = eptrtmp;
		}
	}

	for (i = 0; i < dli_nlevels; i++) {
		memset(dlip[i], 0, sizeof(struct dli));
		myfree(dlip[i], __FUNCTION__, __LINE__);
		dlip[i] = NULL;
	}

	memset(dlip, 0, (dli_nlevels * sizeof(struct dli *)));
	myfree(dlip, __FUNCTION__, __LINE__);

	/* no layers data */
	dli_nlevels = 0;
	dlip = NULL;

	return;
}

/* fresh node */
struct unode *unode_new(char *name)
{
	struct unode *un = NULL;

	un = mymalloc(sizeof(struct unode), __FUNCTION__, __LINE__);

	/* uniq node number for regular, dummy and edgelabel nodes */
	un->number = uniq_node_number;

	uniq_node_number = (uniq_node_number + 1);

	/* default to name and label the same */
	un->name = (char *)name;
	un->label = (char *)name;

	un->fillcolor = 0x00ffffff;	/* white fill color */

	return ((struct unode *)un);
}

/* fresh dummy node */
struct unode *udummynode_new(void)
{
	struct unode *un = NULL;
	char buf[32];
	char *name = NULL;

	memset(buf, 0, 32);

	snprintf(buf, (32 - 1), "__dummynode%d__", uniq_node_number);

	name = uniqstring(buf);

	un = unode_new(name);

	un->name = (char *)name;

	/* indicate this is a dummynode without display name */
	un->label = NULL;
	un->fillcolor = 0x00ffffff;	/* white fill color */
	un->bitflags.dummynode = 1;

	return ((struct unode *)un);
}

/* fresh edgelabel node */
struct unode *uedgelabel_new(char *label)
{
	struct unode *un = NULL;
	char buf[32];
	char *name = NULL;

	memset(buf, 0, 32);

	snprintf(buf, (32 - 1), "__edgelabel%d__", uniq_node_number);

	/* strdup() string */
	name = uniqstring(buf);

	/* new node */
	un = unode_new(name);

	/* set uniq node name */
	un->name = (char *)name;

	/* indicate this is a edgelabel node with display name */
	un->label = label;

	/* border and background color is not drawn at edgelabel and box uses less space of node shapes */
	un->bitflags.shape = NSHAPE_BOX;

	/* set bit to indicate this node is not a node but edgelabel to draw different */
	un->bitflags.edgelabel = 1;

	return ((struct unode *)un);
}

/* fresh edge */
struct uedge *uedge_new(struct unode *fn, struct unode *tn)
{
	struct uedge *ue = NULL;
	ue = mymalloc(sizeof(struct uedge), __FUNCTION__, __LINE__);
	/* set uniq number */
	ue->number = uniq_edge_number;
	uniq_edge_number = (uniq_edge_number + 1);
	/* set from/to node of this edge */
	ue->fn = fn;
	ue->tn = tn;
	/* draw arrows at edge */
	ue->bitflags.arrows = 1;
	/* do not draw arrow at both edge side */
	ue->bitflags.botharrows = 0;
	/* do not draw multiple arrows at long edge */
	ue->bitflags.multarrows = 0;
	return ((struct uedge *)ue);
}

/* fresh subgraph */
struct usubg *usubg_new(char *name, struct usubg *rootedon)
{
	struct usubg *nsg = NULL;
	nsg = mymalloc(sizeof(struct usubg), __FUNCTION__, __LINE__);
	/* set uniq number */
	nsg->number = uniq_subgraph_number;
	uniq_subgraph_number = (uniq_subgraph_number + 1);
	/* subgraph name ref */
	nsg->name = name;
	nsg->label = name;
	/* unfolded subgraph */
	nsg->bitflags.folded = 0;
	/* subgraph rooted on other subgraph or rootgraph if NULL */
	nsg->rootedon = rootedon;
	/* summary node for folded subgraph */
	nsg->summaryn = unode_new(name);
	/* box with doubled border shape */
	nsg->summaryn->bitflags.shape = NSHAPE_DBOX;
	/* indicate a summary node */
	nsg->summaryn->bitflags.sumnode = 1;
	/* draw summary node label as shadowed text as easy visual */
	nsg->summaryn->bitflags.textshadow = 1;
	/* draw summary node label as bold text as easy visual */
	nsg->summaryn->bitflags.textbold = 1;
	/* summary node part of this graph */
	nsg->summaryn->rootedon = nsg;
	return ((struct usubg *)nsg);
}

/* copy edge attributes */
void uedge_copy_attribs(struct uedge *from, struct uedge *to)
{

	if ((from == (struct uedge *)0) || (to == (struct uedge *)0)) {
		/* shouldnothappen */
		return;
	}

	/* skip int number; uniq number */
	/* skip struct unode *fn; from node */
	/* skip struct unode *tn; to node */
	to->rootedon = from->rootedon;	/* edge is defined in subgraph but may be located in other subgraph */
	to->color = from->color;	/* color of edge line a/r/g/b */
	to->label = from->label;	/* edgelabel or null */
	to->utf8label = from->utf8label;	/* utf-8 edgelabel or null */
	to->textcolor = from->textcolor;	/* color of label text */
	to->fontsize = from->fontsize;	/* size of font for label text range 1..100 and 0 is gtk default */
	to->fontname = from->fontname;	/* name of font to use default "serif" used if NULL */
	to->tx = from->tx;	/* textarea x-size */
	to->ty = from->ty;	/* textarea y-size */
	to->bbx = from->bbx;	/* total area size with text x-size */
	to->bby = from->bby;	/* total area size with text y-size */
	to->repeated = from->repeated;	/* edge is n times repeated in input graph */
	to->bitflags = from->bitflags;

	return;
}

/* fresh node link */
struct dln *dln_new(void)
{
	struct dln *ndln = NULL;
	ndln = mymalloc(sizeof(struct dln), __FUNCTION__, __LINE__);
	return ((struct dln *)ndln);
}

/* fresh draw node */
struct drawn *drawn_new(void)
{
	struct drawn *ndn = NULL;
	ndn = mymalloc(sizeof(struct drawn), __FUNCTION__, __LINE__);
	return ((struct drawn *)ndn);
}

/* fresh draw edge */
struct drawe *drawe_new(void)
{
	struct drawe *nde = NULL;
	nde = mymalloc(sizeof(struct drawe), __FUNCTION__, __LINE__);
	return ((struct drawe *)nde);
}

/* fresh draw node linkage */
struct ddn *ddn_new(void)
{
	struct ddn *nddn = NULL;
	nddn = mymalloc(sizeof(struct ddn), __FUNCTION__, __LINE__);
	return ((struct ddn *)nddn);
}

/* fresh draw edge linkage */
struct dde *dde_new(void)
{
	struct dde *ndde = NULL;
	ndde = mymalloc(sizeof(struct dde), __FUNCTION__, __LINE__);
	return ((struct dde *)ndde);
}

/* fresh draw levels info */
struct dli *dli_new(void)
{
	struct dli *ndli = NULL;
	ndli = mymalloc(sizeof(struct dli), __FUNCTION__, __LINE__);
	return ((struct dli *)ndli);
}

/* add virtual node to virtual node list */
void virtualnl_add(struct unode *un)
{

	if (sp_virtualnl == (splay_tree) 0) {
		sp_virtualnl = splay_tree_new(splay_tree_compare_ints, NULL, splay_tree_free_value);
	}

	splay_tree_insert(sp_virtualnl, (splay_tree_key) un->number, (splay_tree_value) un);

	return;
}

/* add virtual edge to virtual edge list */
void virtualel_add(struct uedge *ue)
{

	if (sp_virtualel == (splay_tree) 0) {
		sp_virtualel = splay_tree_new(splay_tree_compare_ints, NULL, splay_tree_free_value);
	}

	splay_tree_insert(sp_virtualel, (splay_tree_key) ue->number, (splay_tree_value) ue);

	return;
}

/* add to parsed node list */
void parsednl_add(struct unode *un)
{
	if (un == (struct unode *)0) {
		return;
	}

	if (sp_parsednl == (splay_tree) 0) {
		sp_parsednl = splay_tree_new(splay_tree_compare_ints, NULL, splay_tree_free_value);
	}

	splay_tree_insert(sp_parsednl, (splay_tree_key) un->number, (splay_tree_value) un);

	return;
}

/* add node to summary nodes list */
void summarynl_add(struct unode *un)
{

	if (sp_summarynl == (splay_tree) 0) {
		sp_summarynl = splay_tree_new(splay_tree_compare_ints, NULL, NULL);
	}

	splay_tree_insert(sp_summarynl, (splay_tree_key) un->number, (splay_tree_value) un);

	return;
}

/* add node to work summary nodes list */
void wsummarynl_add(struct unode *un)
{

	if (sp_wsummarynl == (splay_tree) 0) {
		sp_wsummarynl = splay_tree_new(splay_tree_compare_ints, NULL, NULL);
	}

	splay_tree_insert(sp_wsummarynl, (splay_tree_key) un->number, (splay_tree_value) un);

	return;
}

/* add to parsed work node list */
void parsedwnl_add(struct unode *un)
{

	if (sp_parsedwnl == (splay_tree) 0) {
		sp_parsedwnl = splay_tree_new(	/* The comparision function.  */
						     (splay_tree_compare_fn) splay_tree_compare_ints,
						     /* The deallocate-key function.  NULL if no cleanup is necessary.  */
						     (splay_tree_delete_key_fn) 0,
						     /* The deallocate-value function.  NULL if no cleanup is necessary.  */
						     (splay_tree_delete_value_fn) 0);
	}

	splay_tree_insert(sp_parsedwnl, (splay_tree_key) un->number, (splay_tree_value) un);

	return;
}

/* add to parsed edge list */
void parsedel_add(struct uedge *ue)
{

	if (ue == (struct uedge *)0) {
		return;
	}

	if (sp_parsedel == (splay_tree) 0) {
		sp_parsedel = splay_tree_new(splay_tree_compare_ints, NULL, splay_tree_free_value);
	}

	splay_tree_insert(sp_parsedel, (splay_tree_key) ue->number, (splay_tree_value) ue);

	return;
}

/* add to parsed work edge list */
void parsedwel_add(struct uedge *ue)
{

	if (sp_parsedwel == (splay_tree) 0) {
		/* create copy of parsed edges to work on. */
		sp_parsedwel = splay_tree_new(	/* The comparision function.  */
						     (splay_tree_compare_fn) splay_tree_compare_ints,
						     /* The deallocate-key function.  NULL if no cleanup is necessary.  */
						     (splay_tree_delete_key_fn) 0,
						     /* The deallocate-value function.  NULL if no cleanup is necessary.  */
						     (splay_tree_delete_value_fn) 0);
	}

	splay_tree_insert(sp_parsedwel, (splay_tree_key) ue->number, (splay_tree_value) ue);

	return;
}

/* add subgraph to parsed subgraph list */
void parsedsgl_add(struct usubg *subg)
{

	/* subgraph in root graph or subgraph */
	if (subg->rootedon == NULL) {
		/* subgraph rooted on root graph */
		if (sp_parsedsgl == (splay_tree) 0) {
			sp_parsedsgl = splay_tree_new(splay_tree_compare_ints, NULL, splay_tree_free_value);
		}

		splay_tree_insert(sp_parsedsgl, (splay_tree_key) subg->number, (splay_tree_value) subg);
	} else {
		/* subgraph rooted on other subgraph */
		if (subg->rootedon->sp_sg == (splay_tree) 0) {
			subg->rootedon->sp_sg = splay_tree_new(splay_tree_compare_ints, NULL, splay_tree_free_value);
		}

		splay_tree_insert(subg->rootedon->sp_sg, (splay_tree_key) subg->number, (splay_tree_value) subg);

	}

	return;
}

/* add node to parsed subgraph list */
static void parsedsgl_add_node(struct unode *un)
{

	/* node is in root graph or subgraph */
	if (un->rootedon == NULL) {
		/* node in root graph */
		if (sp_rootnl == (splay_tree) 0) {
			sp_rootnl = splay_tree_new(splay_tree_compare_ints, NULL, NULL);
		}
		splay_tree_insert(sp_rootnl, (splay_tree_key) un->number, (splay_tree_value) un);
	} else {
		/* node in subgraph */
		if (un->rootedon->sp_nl == (splay_tree) 0) {
			un->rootedon->sp_nl = splay_tree_new(splay_tree_compare_ints, NULL, NULL);
		}

		splay_tree_insert(un->rootedon->sp_nl, (splay_tree_key) un->number, (splay_tree_value) un);

	}

	return;
}

/* add edge to parsed subgraph list */
static void parsedsgl_add_edge(struct uedge *ue)
{

	/* check if edge crosses subgraphs */
	if (ue->fn->rootedon == ue->tn->rootedon) {
		/* edge is inside subgraph */
		/* from node node is in root graph or subgraph */
		if (ue->fn->rootedon == NULL) {
			/* edge in root graph */
			if (sp_rootel == (splay_tree) 0) {
				sp_rootel = splay_tree_new(splay_tree_compare_ints, NULL, NULL);
			}
			splay_tree_insert(sp_rootel, (splay_tree_key) ue->number, (splay_tree_value) ue);
		} else {
			/* edge in subgraph */
			if (ue->fn->rootedon->sp_el == (splay_tree) 0) {
				ue->fn->rootedon->sp_el = splay_tree_new(splay_tree_compare_ints, NULL, NULL);
			}
			splay_tree_insert(ue->fn->rootedon->sp_el, (splay_tree_key) ue->number, (splay_tree_value) ue);
		}
	} else {
		/* edge is crossing subgraphs */
		/* from node node is in root graph or subgraph */
		if (ue->fn->rootedon == NULL) {
			/* edge in root graph */
			if (sp_rootel == (splay_tree) 0) {
				sp_rootel = splay_tree_new(splay_tree_compare_ints, NULL, NULL);
			}
			splay_tree_insert(sp_rootel, (splay_tree_key) ue->number, (splay_tree_value) ue);
		} else {
			/* edge in subgraph */
			if (ue->fn->rootedon->sp_el == (splay_tree) 0) {
				ue->fn->rootedon->sp_el = splay_tree_new(splay_tree_compare_ints, NULL, NULL);
			}
			splay_tree_insert(ue->fn->rootedon->sp_el, (splay_tree_key) ue->number, (splay_tree_value) ue);
		}

		/* to node node is in root graph or subgraph */
		if (ue->tn->rootedon == NULL) {
			/* edge in root graph */
			if (sp_rootel == (splay_tree) 0) {
				sp_rootel = splay_tree_new(splay_tree_compare_ints, NULL, NULL);
			}
			splay_tree_insert(sp_rootel, (splay_tree_key) ue->number, (splay_tree_value) ue);
		} else {
			/* edge in subgraph */
			if (ue->tn->rootedon->sp_el == (splay_tree) 0) {
				ue->tn->rootedon->sp_el = splay_tree_new(splay_tree_compare_ints, NULL, NULL);
			}
			splay_tree_insert(ue->tn->rootedon->sp_el, (splay_tree_key) ue->number, (splay_tree_value) ue);
		}
	}

	return;
}

/* clear nl and el in root and subgraphs */
static void clear_subg_nel1(struct usubg *subg)
{
	struct usubg *sg = (struct usubg *)0;
	splay_tree_node spn = (splay_tree_node) 0;

	/* if no subgraph oke */
	if (subg == NULL) {
		return;
	}

	/* clear subgraph node list */
	subg->sp_nl = splay_tree_delete(subg->sp_nl);

	/* clear subgraph edge list */
	subg->sp_el = splay_tree_delete(subg->sp_el);

	if (splay_tree_has_data(subg->sp_sg)) {

		spn = splay_tree_min(subg->sp_sg);

		/* recurse in deeper subgraphs */
		while (spn) {
			sg = (struct usubg *)spn->value;
			clear_subg_nel1(sg);
			spn = splay_tree_successor(subg->sp_sg, spn->key);
		}
	}

	/* delete working subgraph list */
	subg->sp_wsg = splay_tree_delete(subg->sp_wsg);

	return;
}

/* clear nl and el in root and subgraphs */
void clear_subg_nel(void)
{
	struct usubg *sg = (struct usubg *)0;
	splay_tree_node spn = (splay_tree_node) 0;

	/* clear root graph node list */
	sp_rootnl = splay_tree_delete(sp_rootnl);

	/* clear root graph edge list */
	sp_rootel = splay_tree_delete(sp_rootel);

	/* clear subgraph nl and el */
	if (splay_tree_has_data(sp_parsedwsgl)) {

		spn = splay_tree_min(sp_parsedwsgl);

		while (spn) {
			sg = (struct usubg *)spn->value;
			clear_subg_nel1(sg);
			spn = splay_tree_successor(sp_parsedwsgl, spn->key);
		}
	}

	return;
}

/* refresh nl and el lists in root and subgraph */
void rebuild_subg_nel(void)
{
	splay_tree_node spn = (splay_tree_node) 0;
	struct unode *un = (struct unode *)0;
	struct uedge *ue = (struct uedge *)0;

	/* clear nl and el in root and subgraphs */
	clear_subg_nel();

	/* check if something todo. */
	if (splay_tree_has_data(sp_parsedwnl) == 0) {
		return;
	}

	/* scan working nodes */
	spn = splay_tree_min(sp_parsedwnl);

	while (spn) {
		un = (struct unode *)spn->value;

		/* copy node in the sub/root graph struct */
		parsedsgl_add_node(un);

		spn = splay_tree_successor(sp_parsedwnl, spn->key);
	}

	/* edge data is optional */
	if (splay_tree_has_data(sp_parsedwel)) {

		spn = splay_tree_min(sp_parsedwel);

		while (spn) {
			ue = (struct uedge *)spn->value;

			/* copy edge in root/subgraph struct */
			parsedsgl_add_edge(ue);

			spn = splay_tree_successor(sp_parsedwel, spn->key);
		}

	}

	return;
}

/* add to draw nodes list */
void drawnl_add(struct drawn *node)
{
	/* draw nodes list end */
	if (drawnl_end == NULL) {
		drawnl = node;
		drawnl_end = node;
	} else {
		drawnl_end->next = node;
		drawnl_end = node;
	}

	return;
}

/* add to draw edges list */
void drawel_add(struct drawe *edge)
{
	/* draw edges list end */
	if (drawel_end == NULL) {
		drawel = edge;
		drawel_end = edge;
	} else {
		drawel_end->next = edge;
		drawel_end = edge;
	}

	return;
}

/* add draw node to draw layer information */
void dli_add_node(struct dli *lp, struct ddn *node)
{

	if (lp->nl_end == NULL) {
		/* first entry */
		lp->nl = node;
		lp->nl_end = node;
	} else {
		lp->nl_end->next = node;
		lp->nl_end = node;
	}

	return;
}

/* add draw edge to draw layer information */
void dli_add_edge(struct dli *lp, struct dde *edge)
{

	if (lp->el_end == NULL) {
		/* first entry */
		lp->el = edge;
		lp->el_end = edge;
	} else {
		lp->el_end->next = edge;
		lp->el_end = edge;
	}

	return;
}

/* add edge to part-of-edge list in node */
void unode_poe_add(struct unode *un, struct uedge *ue)
{

	if (un->sp_poe == (splay_tree) 0) {
		un->sp_poe = splay_tree_new(splay_tree_compare_ints, NULL, NULL);
	}

	splay_tree_insert(un->sp_poe, (splay_tree_key) ue->number, (splay_tree_value) ue);

	return;
}

/* rebuild part-of-edge list in nodes */
void rebuild_poe(void)
{
	splay_tree_node spn = (splay_tree_node) 0;
	struct unode *un = (struct unode *)0;
	struct uedge *ue = (struct uedge *)0;

	/* return if no node data */
	if (splay_tree_has_data(sp_parsedwnl) == 0) {
		return;
	}

	/* scan the work nodes */
	spn = splay_tree_min(sp_parsedwnl);

	while (spn) {
		un = (struct unode *)spn->value;

		/* wipe old list if exists */
		un->sp_poe = splay_tree_delete(un->sp_poe);

		/* dummy node in/out edge */
		un->din = (struct uedge *)0;
		un->dout = (struct uedge *)0;

		/* zero in/out degree */
		un->indegree = 0;
		un->outdegree = 0;

		spn = splay_tree_successor(sp_parsedwnl, spn->key);
	}

	/* scan the work edges */
	spn = splay_tree_min(sp_parsedwel);

	while (spn) {
		ue = (struct uedge *)spn->value;

		/* extra inline check */
		if ((ue->bitflags.done == 0) || (ue->bitflags.visible == 0)) {
			printf
			    ("%s(): done=%d visible=%d in edge %s->%s (expected both bits set)\n",
			     __FUNCTION__, (int)ue->bitflags.done, (int)ue->bitflags.visible, ue->fn->name, ue->tn->name);
			fflush(stdout);
		}

		/* add edge as part of from node */
		unode_poe_add(ue->fn, ue);

		/* update outdegree */
		ue->fn->outdegree = (ue->fn->outdegree + 1);

		/* outgoing edge at dummy node */
		ue->fn->dout = ue;

		/* add edge as part of to node */
		unode_poe_add(ue->tn, ue);

		/* update indegree */
		ue->tn->indegree = (ue->tn->indegree + 1);

		/* incoming edge at dummy node */
		ue->tn->din = ue;

		/* next working edge */
		spn = splay_tree_successor(sp_parsedwel, spn->key);
	}

	return;
}

/* seems to be the right way todo rand() */
int rg_rand(int maxval)
{
	double ff = 0.0;
	int r = 0;
	r = rand();
	r++;
	/* return 0..maxval */
	ff = (floor((double)r / RAND_MAX * maxval));
	return ((int)ff);
}

/* generate new "parsed" random graph */
void randomgraph(void)
{
	int i = 0;
	int nodes = 0;
	int edges = 0;
	int layers = 0;
	int branching = 0;
	double max_edges = 0.0;
	struct rg_node_struct *nnode = NULL;
	struct unode *un = NULL;
	struct rg_edge_struct *nedge = NULL;
	struct uedge *ue = NULL;
	struct unode *fn = NULL;
	struct unode *tn = NULL;
	int big = 0;

	/* set to 1 for big graph */
	big = 0;

	/* */
	nodes = 8 + rg_rand(10);
	edges = (nodes - 1) + rg_rand(10);

	if (big) {
		/* 2*1024*100 oke, can go up to 4.8 million without problems */
		nodes = 8 * 1000 * 100;
		edges = 8 * 1000 * 100;
	}

	if (edges < (nodes - 1)) {	/* error */
	}

	max_edges = (double)((nodes * nodes) / 4);

	if (edges > max_edges) {	/* error */
	}

	layers = 6 + rg_rand(5);
	branching = 8 + rg_rand(3);

	if (big) {
		layers = layers * 10000;
		branching = branching * 10000;
	}

	/* */
	rg_number_of_nodes = 0;

	/* */
	rg_number_of_tree_nodes = 0;

	/* */
	rg_number_of_edges = 0;

	/* create random tree and add random edges to the tree to create a random dag */
	rg_dag(nodes, edges, layers, branching);

	/* random add self-edges */
	if (rg_rand(100) > 50) {
		if (0) {
			printf("%s(): rd_add_selfedges()\n", __FUNCTION__);
		}
	}

	/* random add single-nodes */
	if (rg_rand(100) > 50) {
		if (0) {
			printf("%s(): rg_add_singlenodes()\n", __FUNCTION__);
		}
	}

	/* set random drawing background color */
	rg_backgroundcolor();

	/* copy into parsed data nodes */
	for (i = 0; i < rg_number_of_nodes; i++) {
		nnode = rg_master_node_list[i];
		un = unode_new(nnode->name);

		/* use node name as label option */
		if (option_nodenames) {
			/* unode_new() did set the label */
		} else {
			/* set random lorus ipsum label text */
			un->label = rg_labelstring();
		}

		/* set fontsize */
		un->fontsize = rg_fontsize_numberstring();
		/* default fontname */
		un->fontname = NULL;
		/* random bold font */
		if (rg_rand(100) > 50) {
			un->bitflags.textbold = 1;
		}
		/* random italic font */
		if (rg_rand(100) > 50) {
			un->bitflags.textitalic = 1;
		}
		/* put node in current root graph */
		un->rootedon = NULL;
		/* random node shape */
		un->bitflags.shape = rg_nodeshape();
		/* random node color */
		un->fillcolor = rg_nodecolor();
		/* random node textcolor */
		un->textcolor = rg_nodetextcolor();
		/* node is defined by node statement */
		un->bitflags.defbynode = 1;
		/* */
		parsednl_add(un);
		uniqnode_add(un->name, un);
	}

	/* copy into parsed data edges */
	for (i = 0; i < rg_number_of_edges; i++) {
		nedge = rg_master_edge_list[i];
		fn = uniqnode(nedge->down_node->name);
		if (fn == (struct unode *)0) {
			printf("%s(): could not get fn uniqnode for %s\n", __FUNCTION__, nedge->down_node->name);
			fflush(stdout);
			return;
		}
		tn = uniqnode(nedge->up_node->name);
		if (tn == (struct unode *)0) {
			printf("%s(): could not get tn uniqnode for %s\n", __FUNCTION__, nedge->down_node->name);
			fflush(stdout);
			return;
		}
		ue = uedge_new(fn, tn);
		/* black edge line or colored */
		if (rg_rand(100) > 50) {
			ue->color = rg_edgecolor();
		}
		/* optional edge label cannot be done here because it needs extra levels
		 * if ((rand () % 100) > 90)
		 * {
		 * ue->label = s;
		 * }
		 */
		/* solid or other style edge line */
		ue->bitflags.style = rg_edgestyle();
		/* random thickness or 0 as default */
		ue->bitflags.thickness = rg_rand(3);
		/* edge created in root graph */
		ue->rootedon = NULL;
		parsedel_add(ue);
	}

	/* clear nodes */
	for (i = 0; i < rg_number_of_nodes; i++) {
		myfree(rg_master_node_list[i], __FUNCTION__, __LINE__);
		rg_master_node_list[i] = NULL;
	}

	/* */
	myfree(rg_master_node_list, __FUNCTION__, __LINE__);
	rg_master_node_list = NULL;

	/* clear edges */
	for (i = 0; i < rg_number_of_edges; i++) {
		myfree(rg_master_edge_list[i], __FUNCTION__, __LINE__);
		rg_master_edge_list[i] = NULL;
	}

	/* */
	myfree(rg_master_edge_list, __FUNCTION__, __LINE__);
	rg_master_edge_list = NULL;

	/* clear layers data */
	for (i = 0; i < layers; i++) {
		if (rg_layers[i]->nodes) {
			myfree(rg_layers[i]->nodes, __FUNCTION__, __LINE__);
		}
		rg_layers[i]->nodes = NULL;
		myfree(rg_layers[i], __FUNCTION__, __LINE__);
		rg_layers[i] = NULL;
	}

	myfree(rg_layers, __FUNCTION__, __LINE__);
	rg_layers = NULL;

	/* clear node direction table */
	myfree(rg_going_up, __FUNCTION__, __LINE__);
	rg_going_up = NULL;

	/* */
	rg_number_of_nodes = 0;
	rg_number_of_tree_nodes = 0;
	rg_number_of_edges = 0;
	rg_number_of_layers = 0;

	return;
}

/* set random node text color - dark colors */
static unsigned int rg_nodetextcolor(void)
{
	unsigned int color = 0;
	int rc = 0;
	const char *colorname = NULL;

	rc = rg_rand(5);

	switch (rc) {
	case 0:
		colorname = "black";
		break;
	case 1:
		colorname = "black";
		break;
	case 2:
		colorname = "NavyBlue";
		break;
	case 3:
		colorname = "DarkBlue";
		break;
	case 4:
		colorname = "DarkGreen";
		break;
	case 5:
		colorname = "DarkRed";
		break;
	default:
		colorname = "black";
		break;
	}

	color = colorcode(colorname);

	return (color);

}

/* set random node color - light colors */
static unsigned int rg_nodecolor(void)
{
	unsigned int color = 0;
	int rc = 0;
	const char *colorname = NULL;

	rc = rg_rand(10);

	switch (rc) {
	case 0:
		colorname = "white";
		break;
	case 1:
		colorname = "white";
		break;
	case 2:
		colorname = "lightgray";
		break;
	case 3:
		colorname = "lightskyblue";
		break;
	case 4:
		colorname = "azure";
		break;
	case 5:
		colorname = "cyan";
		break;
	case 6:
		colorname = "yellow1";
		break;
	case 7:
		colorname = "snow";
		break;
	case 8:
		colorname = "lightsalmon";
		break;
	case 9:
		colorname = "WhiteSmoke";
		break;
	default:
		colorname = "white";
		break;
	}

	color = colorcode(colorname);

	if (color == 0) {
		printf("%s(): warning black fillcolor shouldnothappen\n", __FUNCTION__);
		/* make it white */
		color = 0x00ffffff;
	}

	return (color);
}

/* set random node shape */
static unsigned char rg_nodeshape(void)
{
	unsigned char shape = 0;
	int rc = 0;

	rc = rg_rand(40);

	switch (rc) {
	case 0:
		shape = NSHAPE_ELLIPS;
		break;
	case 1:
		shape = NSHAPE_CIRCLE;
		break;
	case 2:
		shape = NSHAPE_BOX;
		break;
	case 3:
		shape = NSHAPE_RBOX;
		break;
	case 4:
		shape = NSHAPE_CARD;
		break;
	case 5:
		shape = NSHAPE_CLOUD;
		break;
	case 6:
		shape = NSHAPE_DBOX;
		break;
	case 7:
		shape = NSHAPE_DIAMOND;
		break;
	case 8:
		shape = NSHAPE_MDIAMOND;
		break;
	case 9:
		shape = NSHAPE_HEXAGON;
		break;
	case 10:
		shape = NSHAPE_PENTAGON;
		break;
	case 11:
		shape = NSHAPE_FOLDER;
		break;
	case 12:
		shape = NSHAPE_SBOX;
		break;
	case 13:
		shape = NSHAPE_CUBE;
		break;
	case 14:
		shape = NSHAPE_RCLOUD;	/* round cloud */
		break;
	case 15:
		shape = NSHAPE_CHEVRON;
		break;
	case 16:
		shape = NSHAPE_CYLINDER;
		break;
	case 17:
		shape = NSHAPE_DIALOG;
		break;
	case 18:
		shape = NSHAPE_MAXIMIZE;
		break;
	case 19:
		shape = NSHAPE_PAGE;
		break;
	case 20:
		shape = NSHAPE_PLAQUE;
		break;
	case 21:
		shape = NSHAPE_PREP;
		break;
	case 22:
		shape = NSHAPE_PUNCHED;
		break;
	case 23:
		shape = NSHAPE_SEPTAGON;
		break;
	case 24:
		shape = NSHAPE_SHIELD;
		break;
	case 25:
		shape = NSHAPE_STORED;
		break;
	case 26:
		shape = NSHAPE_TRAPEZOID;
		break;
	case 27:
		shape = NSHAPE_TRIANGLE;
		break;
	case 28:
		shape = NSHAPE_VSCROLL;
		break;
	case 29:
		shape = NSHAPE_ITRIANGLE;
		break;
	default:
		shape = NSHAPE_DEFAULT;
		break;
	}

	return ((unsigned char)shape);
}

/* return random fontsize number as string */
static char *rg_fontsize_numberstring(void)
{
	char buf[4];
	int num = 0;
	char *s = NULL;
	memset(buf, 0, 4);
	num = rg_rand(5);
	num = num + 5;
	snprintf(buf, (4 - 1), "%d", num);
	s = uniqstring(buf);
	return (s);
}

/* return random number as string */
static char *rg_numberstring(void)
{
	char buf[5];
	int num = 0;
	char *s = NULL;
	memset(buf, 0, 5);
	num = rg_rand(1234);
	snprintf(buf, (5 - 1), "%d", num);
	s = uniqstring(buf);
	return (s);
}

/* return random ipsum label string */
static char *rg_labelstring(void)
{
	char buf[1024];
	char *s = NULL;
	char *p = NULL;
	int num = 0;
	int nlines = 0;
	int nwol = 0;
	int i = 0;
	int ii = 0;

	(void)memset(buf, 0, 1024);

	nlines = (1 + rg_rand(2));
	p = buf;

	/* number of words-on-a-line */
	nwol = (1 + rg_rand(2));

	/* create single word single line nodes */
	if ((nlines == 1) || (nwol == 1)) {
		nlines = 1;
		nwol = 1;
	}

	/* create the lines with words on it */
	for (i = 0; i < nlines; i++) {
		for (ii = 0; ii < nwol; ii++) {
			/* random lorus ipsum word or a number */
			num = rg_rand(30);

			switch (num) {
			case 0:
				s = "Linux Rulezzz";
				break;
			case 1:
				s = "tah.bet";
				break;
			case 2:
				s = "sfs.bet";
				break;
			case 3:
				s = "qrovna.bet";
				break;
			case 4:
				s = "Linux Rulezzz";
				break;
			case 5:
				s = "fsf.org";
				break;
			case 6:
				s = "tah.bet";
				break;
			case 7:
				s = "Linux Rulezzz";
				break;
			case 8:
				s = "Free";
				break;
			case 9:
				s = "fgnyyzna.bet";
				break;
			case 10:
				s = "Yvahk Ehyrmm";
				break;
			case 11:
				s = "bcrafhfr.bet";
				break;
			case 12:
				s = "sfsr.bet";
				break;
			case 13:
				s = "erqung.pbz";
				break;
			case 14:
				s = "Linux";
				break;
			case 15:
				s = "TPP";
				break;
			case 16:
				s = "xreary.bet";
				break;
			case 17:
				s = "zbbvtencu";
				break;
			case 18:
				s = "ghkfrr";
				break;
			case 19:
				s = "Yvoer";
				break;
			case 20:
				s = "xqr.bet";
				break;
			case 21:
				s = "tabzr.bet";
				break;
			case 22:
				s = "funer gur fbsgjner";
				break;
			case 23:
				s = "Yvahk ehyrmm";
				break;
			case 24:
				s = "rss.bet";
				break;
			case 25:
				s = "fhtvlnzn";
				break;
			case 26:
				s = "Linux Rulezzz";
				break;
			case 27:
				s = "tuxsee";
				break;
			case 29:
				s = "Linux Rulezzz";
				break;
			default:
				s = rg_numberstring();
				break;
			}
			p = strcat(p, s);
			p = strcat(p, " ");
		}

		if (p == NULL) {	/* safety */
			p = "empty";
		}

		p = strcat(p, "\n");

		if (strlen(buf) > 1000) {
			break;
		}
	}

	/* erase the last \n in buf */
	i = strlen(buf);

	if (i > 1) {
		buf[i - 1] = 0;
	}

	/* strdup */
	s = uniqstring(buf);

	return (s);
}

/* set random drawing background color - light colors */
static void rg_backgroundcolor(void)
{
	unsigned int color = 0;
	int rc = 0;
	const char *colorname = NULL;

	rc = rg_rand(10);

	switch (rc) {
	case 0:
		colorname = "white";
		break;
	case 1:
		colorname = "white";
		break;
	case 2:		/* mint */
		colorname = "mintcream";
		break;
	case 3:		/* light grey */
		colorname = "gray77";
		break;
	case 4:		/* blue */
		colorname = "lightskyblue";
		break;
	case 5:		/* green */
		colorname = "springgreen";
		break;
	case 6:		/* gold */
		colorname = "gold";
		break;
	case 7:		/* yellow */
		colorname = "lightyellow";
		break;
	case 8:		/* yellow */
		colorname = "yellow";
		break;
	case 9:		/* blue */
		colorname = "aliceblue";
		break;
	default:
		colorname = "white";
		break;
	}

	/* get color code for named color */
	color = colorcode(colorname);

	/* set drawing background color */
	bgcr = (color & 0x00ff0000) >> 16;
	bgcg = (color & 0x0000ff00) >> 8;
	bgcb = (color & 0x000000ff);

	return;
}

/* return random int a/r/g/b for edge color - dark colors */
static unsigned int rg_edgecolor(void)
{
	unsigned int color = 0;
	int num = 0;

	/* choose out of ten colors */
	num = rg_rand(10);

	switch (num) {
	case 0:
		color = colorcode("DarkBlue");
		break;
	case 1:
		color = colorcode("CadetBlue");
		break;
	case 2:
		color = colorcode("DarkCyan");
		break;
	case 3:
		color = colorcode("DarkGreen");
		break;
	case 4:
		color = colorcode("DarkGrey");
		break;
	case 5:
		color = colorcode("DarkRed");
		break;
	case 6:
		color = colorcode("bisque");
		break;
	case 7:
		color = colorcode("blue");
		break;
	case 8:
		color = colorcode("MidnightBlue");
		break;
	case 9:
		color = colorcode("ForestGreen");
		break;
	default:
		color = colorcode("black");
		break;
	}

	return (color);
}

/* return random int for edge style */
static int rg_edgestyle(void)
{
	int style = 0;
	int num = 0;

	/* four edge styles */
	num = rg_rand(4);

	switch (num) {
	case 0:
		style = ESTYLE_SOLID;	/* solid edge line */
		break;
	case 1:
		style = ESTYLE_DOTTED;	/* dotted edge line */
		break;
	case 2:
		style = ESTYLE_DASHED;	/* dashed edge line */
		break;
	case 3:
		style = ESTYLE_SOLID;	/* ESTYLE_INVIS invisible edge line is skipped in random graph */
		break;
	default:
		style = ESTYLE_SOLID;	/* solid edge line */
		break;
	}

	return (style);
}

/* create random graph */
static void rg_dag(int num_nodes, int desired_num_edges, int num_layers, int branching_factor)
{
	int first_node_index = 0;
	int first_node_layer_number = 0;
	struct rg_node_struct *first_node = NULL;
	int second_node_layer_number = 0;
	struct rg_layer_struct *second_node_layer = NULL;
	int second_node_layer_position = 0;
	struct rg_node_struct *second_node = NULL;
	int second_node_index = 0;
	int maxtry = 0;

	/* create a tree graph */
	rg_tree(num_nodes, num_layers, branching_factor);

	/* random keep it a tree or make it a dag
	 * if (rg_rand (100) < 5)
	 * {
	 * return;
	 * }
	 */

	/* limit amount of tries */
	maxtry = 0;

	/* randor add edges to the tree */
	while (desired_num_edges >= rg_number_of_edges) {

		/* number of tries */
		maxtry++;

		/* limit number of tries */
		if (maxtry > 10000) {
			break;
		}

		/*
		 * pick two random nodes that are on adjacent layers
		 * if there' s not already an edge between them, add one
		 * pick a node that's not on layer 0
		 */
		first_node_index = rg_rand(rg_number_of_nodes);
		first_node = rg_master_node_list[first_node_index];
		first_node_layer_number = first_node->layer;

		/* re-try if this node is in layer 0 */
		if (first_node_layer_number == 0) {
			continue;
		}

		/* pick another node on the layer below that of the first node */
		second_node_layer_number = first_node_layer_number - 1;
		second_node_layer = rg_layers[second_node_layer_number];
		second_node_layer_position = rg_rand(second_node_layer->number_of_nodes);
		second_node = second_node_layer->nodes[second_node_layer_position];
		second_node_index = second_node->id;

		/* add the edge if it doesn't already exist */
		if (rg_pair_already_exists(first_node_index, second_node_index) == 0) {
			/* random reverse edge direction */
			if (rg_rand(100) > 50) {
				rg_add_edge(first_node, second_node);
			} else {
				rg_add_edge(second_node, first_node);
			}
		}

	}

	return;
}

/* return 1 if edge exist */
static int rg_pair_already_exists(int first_node_index, int second_node_index)
{
	int i = 0;
	struct rg_edge_struct *nedge = NULL;

	/* copy into parsed data edges */
	for (i = 0; i < rg_number_of_edges; i++) {
		nedge = rg_master_edge_list[i];
		/* from/to node in edge */
		if (nedge->up_node->id == first_node_index) {
			if (nedge->down_node->id == second_node_index) {	/* edge does exist */
				return (1);
			}
		}
	}

	/* edge did not exist */
	return (0);
}

/* create random graph */
static void rg_tree(int num_nodes, int num_layers, int branching_factor)
{
	int i = 0;
	int current_node_id = 0;
	int nodes_remaining = 0;
	int path_length_to_highest_layer = 0;
	int branch_limit = 0;
	int max_branches = 0;
	int out_degree = 0;
	int child_node_id = 0;
	struct rg_node_struct *current_node = NULL;
	struct rg_node_struct *child_node = NULL;

	/* number of nodes in tree */
	rg_number_of_tree_nodes = 0;

	/* number of nodes in the graph */
	rg_number_of_nodes = num_nodes;

	/* */
	rg_layers_remaining = num_layers;

	/* create the nodes */
	rg_create_master_node_list(num_nodes);

	/* */
	rg_init_layers(num_layers);

	/* */
	rg_number_of_layers = num_layers;

	/* */
	rg_init_node_directions(num_nodes);

	/* create node 0, put it on layer 0, and make it the current node */
	current_node_id = 0;

	/* start with node 0 at toplevel layer 0 */
	current_node = rg_master_node_list[current_node_id];

	/* add in layer 0 */
	rg_add_node_to_layer(current_node, 0);

	/* add node to master list */
	rg_add_node_to_list(current_node);

	/*
	 * create the tree as follows
	 * - take the node at the front of the list (current_node_id)
	 * - choose a degree d in the range [1 .. branching_factor]
	 * - put d new nodes at the rear of the list, assign them to the
	 * appropriate layer and add the appropriate edges
	 */
	while (rg_number_of_tree_nodes < rg_number_of_nodes) {

		/*
		 * Need to make sure that there are enough nodes left to ensure that
		 * every layer has nodes: layers_remaining may be 1 even if so; this
		 * ensures that the number of children does not exceed the number of
		 * nodes remaining
		 */
		nodes_remaining = rg_number_of_nodes - rg_number_of_tree_nodes;
		path_length_to_highest_layer = num_layers - 1 - current_node->layer;
		branch_limit = branching_factor;

		/*
		 * need to leave enough nodes for next node to have access to the top
		 * layer; this may turn out to be <= 0, in which case there should be no
		 * branching
		 */
		if (rg_layers_remaining > 0 && branch_limit > nodes_remaining - path_length_to_highest_layer) {
			branch_limit = nodes_remaining - path_length_to_highest_layer;
		}

		/* also, can't have more branches than number of nodes remaining */
		if (branch_limit > nodes_remaining) {
			branch_limit = nodes_remaining;
		}

		/* finally, smooth out the number of nodes in each layer */
		if (current_node->layer == -1) {
			/* node is in undefined layer */
		} else {

			/* */
			if (rg_layers[current_node->layer]->number_of_nodes > num_nodes / num_layers) {
				branch_limit = 1;
			}
		}

		/* */
		max_branches = branching_factor > branch_limit ? branch_limit : branching_factor;

		/* */
		out_degree = 0;

		/* */
		if (max_branches > 0) {
			out_degree = rg_rand(max_branches);
		}

		/* need to have at least one successor if there are no nodes left */
		if (out_degree == 0 && current_node_id + 1 >= rg_number_of_tree_nodes) {
			out_degree = 1;
		}

		/* */
		if (option_ldebug) {
			printf("%s(): Picking # of children: node = %d, remaining = %d,"
			       " path_length = %d, branch_limit = %d"
			       " max_branches = %d, out_degree = %d\n", __FUNCTION__,
			       current_node_id, nodes_remaining, path_length_to_highest_layer, branch_limit, max_branches,
			       out_degree);
			fflush(stdout);
		}

		/* */
		for (i = 0; i < out_degree; i++) {
			child_node_id = rg_number_of_tree_nodes;
			child_node = rg_master_node_list[child_node_id];
			rg_add_node_to_list(child_node);
			rg_assign_child_layer_and_direction(current_node_id, child_node_id);

			/* */
			if (current_node->layer > child_node->layer) {
				rg_add_edge(current_node, child_node);
			} else {
				rg_add_edge(child_node, current_node);
			}
		}

		/* */
		current_node_id++;

		/* */
		current_node = rg_master_node_list[current_node_id];
	}

	return;
}

/* create node */
static struct rg_node_struct *rg_create_node(int node_number)
{
	struct rg_node_struct *new_node = NULL;
	char name_buffer[32];
	char *s = NULL;

	new_node = (struct rg_node_struct *)mymalloc(1 * sizeof(struct rg_node_struct), __FUNCTION__, __LINE__);
	new_node->id = node_number;

	/* give the node a name based on its position in the master list */
	memset(name_buffer, 0, 32);
	snprintf(name_buffer, (32 - 1), "node%d", node_number);
	s = uniqstring(name_buffer);
	new_node->name = s;
	new_node->layer = -1;	/* to indicate "uninitialized" */
	new_node->position = -1;	/* to indicate "uninitialized" */

	return ((struct rg_node_struct *)new_node);
}

/* create nodes */
static void rg_create_master_node_list(int num_nodes)
{
	int i = 0;

	rg_master_node_list =
	    (struct rg_node_struct **)mymalloc(num_nodes * sizeof(struct rg_node_struct *), __FUNCTION__, __LINE__);

	for (i = 0; i < num_nodes; i++) {
		rg_master_node_list[i] = rg_create_node(i);
	}

	return;
}

/* layer table init */
static void rg_init_layers(int num_layers)
{
	int i = 0;

	rg_layers = mymalloc(num_layers * sizeof(struct rg_layer_struct *), __FUNCTION__, __LINE__);

	for (i = 0; i < num_layers; i++) {
		rg_layers[i] = mymalloc(sizeof(struct rg_layer_struct), __FUNCTION__, __LINE__);
		rg_layers[i]->nodes = NULL;
		rg_layers[i]->number_of_nodes = 0;
	}

	return;
}

/* node direction table */
static void rg_init_node_directions(int num_nodes)
{
	int i = 0;

	rg_going_up = mymalloc(num_nodes * sizeof(int), __FUNCTION__, __LINE__);

	for (i = 0; i < num_nodes; i++) {
		rg_going_up[i] = 1;	/* true */
	}

	return;
}

/* add node to given layer */
static void rg_add_node_to_layer(struct rg_node_struct *node, int layer)
{
	struct rg_layer_struct *layer_ptr = NULL;
	struct rg_node_struct **lpn = NULL;

	/* get layer data */
	layer_ptr = rg_layers[layer];

	/* First node on this layer means fewer layers remain */
	if (layer_ptr->number_of_nodes == 0) {
		rg_layers_remaining--;
	}

	/* realloc to a bigger buffer if needed */
	if (layer_ptr->number_of_nodes % 16 == 0) {
		lpn = mymalloc((layer_ptr->number_of_nodes + 16) * sizeof(struct rg_node_struct *), __FUNCTION__, __LINE__);
		if (layer_ptr->nodes != NULL) {
			memmove(lpn, layer_ptr->nodes, (layer_ptr->number_of_nodes) * sizeof(struct rg_node_struct *));
			myfree(layer_ptr->nodes, __FUNCTION__, __LINE__);
		}
		layer_ptr->nodes = lpn;
	}

	/* node is in layer */
	node->layer = layer;

	/* node has position within layer */
	node->position = layer_ptr->number_of_nodes;

	/* */
	layer_ptr->nodes[layer_ptr->number_of_nodes++] = node;

	return;
}

/* add node in master list */
static void rg_add_node_to_list(struct rg_node_struct *node)
{
	rg_master_node_list[rg_number_of_tree_nodes] = node;
	rg_number_of_tree_nodes = (rg_number_of_tree_nodes + 1);
	return;
}

/* */
static void rg_assign_child_layer_and_direction(int parent, int child)
{
	struct rg_node_struct *parent_node = NULL;
	struct rg_node_struct *child_node = NULL;
	int parent_layer = 0;

	/* */
	parent_node = rg_master_node_list[parent];
	child_node = rg_master_node_list[child];
	parent_layer = parent_node->layer;

	rg_going_up[child] = rg_going_up[parent];

	/* handle cases where the path needs to turn around */
	if (rg_going_up[parent] && parent_layer == rg_number_of_layers - 1) {
		rg_going_up[child] = 0;	/* false */
	} else if (!rg_going_up[parent] && parent_layer == 0) {
		rg_going_up[child] = 1;	/* true */
	}

	if (rg_going_up[child] == 1 /* true */ ) {
		child_node->layer = parent_layer + 1;
	} else {
		child_node->layer = parent_layer - 1;
	}

	/* */
	rg_add_node_to_layer(child_node, child_node->layer);

	return;
}

/* */
static void rg_add_edge(struct rg_node_struct *upper_node, struct rg_node_struct *lower_node)
{
	struct rg_edge_struct *new_edge = NULL;
	struct rg_edge_struct **rgm = NULL;

	new_edge = (struct rg_edge_struct *)mymalloc(sizeof(struct rg_edge_struct), __FUNCTION__, __LINE__);
	new_edge->up_node = upper_node;
	new_edge->down_node = lower_node;

	/* add new edge to master edge list, making room if necessary */
	if (rg_number_of_edges % 16 == 0) {
		rgm = mymalloc((rg_number_of_edges + 16) * sizeof(struct rg_edge_struct *), __FUNCTION__, __LINE__);
		if (rg_master_edge_list != NULL) {
			memmove(rgm, rg_master_edge_list, rg_number_of_edges * sizeof(struct rg_edge_struct *));
			myfree(rg_master_edge_list, __FUNCTION__, __LINE__);
		}
		rg_master_edge_list = rgm;
	}

	/* add edge in master */
	rg_master_edge_list[rg_number_of_edges] = new_edge;
	rg_number_of_edges++;

	return;
}

/* calculate input statistics */
static void input_stats_subg(struct usubg *subg)
{
	struct usubg *sg = (struct usubg *)0;
	splay_tree_node spn = (splay_tree_node) 0;

	n_input_subgraphs = 0;

	if (subg == NULL) {
		return;
	}

	/* input number of subgraphs */
	n_input_subgraphs = (n_input_subgraphs + 1);

	if (splay_tree_has_data(subg->sp_sg)) {

		spn = splay_tree_min(subg->sp_sg);

		while (spn) {
			sg = (struct usubg *)spn->value;
			input_stats_subg(sg);
			spn = splay_tree_successor(subg->sp_sg, spn->key);
		}

		/* input number of subgraphs */
		n_input_subgraphs = (n_input_subgraphs + 1);
	}

	return;
}

/* calculate input statistics */
void input_stats(void)
{
	splay_tree_node spn = (splay_tree_node) 0;
	struct unode *un = (struct unode *)0;
	struct uedge *ue = (struct uedge *)0;
	struct usubg *sg = (struct usubg *)0;

	/* input number of nodes */
	n_input_nodes = 0;

	/* input number of singlenodes */
	n_input_singlenodes = 0;

	/* input number of edges */
	n_input_edges = 0;

	/* input number of reversed edges */
	n_input_revedges = 0;

	/* input number of selfedges */
	n_input_selfedges = 0;

	/* input number of edge labels */
	n_input_edgelabels = 0;

	/* input number of subgraphs */
	n_input_subgraphs = 0;

	if (splay_tree_has_data(sp_parsednl)) {

		spn = splay_tree_min(sp_parsednl);

		while (spn) {
			un = (struct unode *)spn->value;
			/* input number of nodes */
			n_input_nodes = (n_input_nodes + 1);
			if (un->bitflags.singlenode) {
				/* input number of singlenodes */
				n_input_singlenodes = (n_input_singlenodes + 1);
			}
			spn = splay_tree_successor(sp_parsednl, spn->key);
		}
	}

	if (splay_tree_has_data(sp_parsedel)) {

		spn = splay_tree_min(sp_parsedel);

		while (spn) {
			ue = (struct uedge *)spn->value;
			/* input number of edges */
			n_input_edges = (n_input_edges + 1);
			if (ue->label) {
				/* input number of edge labels */
				n_input_edgelabels = (n_input_edgelabels + 1);
			}
			if (ue->bitflags.selfedge) {
				/* input number of selfedges */
				n_input_selfedges = (n_input_selfedges + 1);
			}
			spn = splay_tree_successor(sp_parsedel, spn->key);
		}
	}

	if (splay_tree_has_data(sp_parsedsgl)) {

		spn = splay_tree_min(sp_parsedsgl);

		while (spn) {
			sg = (struct usubg *)spn->value;
			input_stats_subg(sg);
			spn = splay_tree_successor(sp_parsedsgl, spn->key);
		}
	}

	return;
}

/* end */
